#pragma once

#include <iostream>
#include <vector>
#include <assert.h>

using std::cout;
using std::endl;
using std::vector;

template <typename T>
class Heap
{
public:
    bool empty() const
    {
        return heap_.empty();
    }

    void push(T val)
    {
        heap_.push_back(val);
        size++;
        comeUp();
    }

    T top() const
    {
        return heap_.front();
    }

    void pop()
    {
        int elms = size - 1, tmp;
        assert(!empty() && "heap is empty()");

        tmp = heap_[elms];
        heap_[elms] = heap_[0];
        heap_[0] = tmp;

        heap_.pop_back();
        size--;

        sink();
    }

    void foreach ()
    {
        for (int i : heap_)
        {
            cout << i << " ";
        }
        cout << endl;
    }

    Heap() {}
    ~Heap() {}

private:
    void comeUp()
    {
        int n = size - 1, val = heap_[n];
        int fatherIdx = (n - 1) / 2;
        while (n > 0 && val > heap_[fatherIdx])
        {
            heap_[n] = heap_[fatherIdx];
            n = fatherIdx;
            fatherIdx = (n - 1) / 2;
        }
        heap_[n] = val;
    }

    void sink()
    {
        int n = 0, val = heap_[0];

        // 一直找到非空的叶子节点
        while (n < size / 2)
        {
            int child = n * 2 + 1;
            if (child + 1 < size && heap_[child + 1] > heap_[child])
            {
                child = child + 1;
            }
            if (heap_[child] > val)
            {
                heap_[n] = heap_[child];
                n = child;
            }else{
                break;
            }
        }
        heap_[n] = val;

    }

private:
    vector<T> heap_;
    size_t size{};
};